package main

import "fmt"

// 如何实现字符串的匹配

func main() {
	s, p := "xyzabcd", "abc"
	fmt.Println(match(s, p))

	s, p = "abaaabaabcbab", "abaabc"
	next := make([]int, len(p)+1)
	getNext(p, next)
	fmt.Println(next)
	fmt.Println(matchKMP(s, p, next))
}

// KMP 算法
func matchKMP(s, p string, next []int) int {
	sLen, pLen := len(s), len(p)
	if sLen < pLen {
		return -1
	}

	i, j := 0, 0
	for i < sLen && j < pLen {
		if j == -1 || s[i] == p[j] {
			i++
			j++
		} else {
			j = next[j]
		}
	}

	if j == pLen {
		return i - pLen
	}

	return -1
}

func getNext(p string, next []int) {
	next[0] = -1
	for i, j := 0, -1; i < len(p); {
		if j == -1 || p[i] == p[j] {
			i++
			j++
			next[i] = j
		} else {
			j = next[j]
		}
	}
}

// 直接计算法
func match(s, p string) int {
	sLen, pLen := len(s), len(p)
	if sLen < pLen {
		return -1
	}

	i, j := 0, 0
	for i < sLen && j < pLen {
		if s[i] == p[j] {
			i++
			j++
		} else {
			i = i - j + 1
			j = 0
			if i > sLen-pLen {
				return -1
			}
		}
	}

	if j == pLen {
		return i - pLen
	}

	return -1
}
